package tianhao.luo.algorithm;

/**
 * 二分查找非递归实现
 *
 * @author: tianhao.luo@hand-china.com 2021/6/28  下午9:24
 */
public class BinarySearchNoRecursion {
    private int[] array;

    public BinarySearchNoRecursion(int[] array) {
        this.array = array;
    }

    /**
     * 二分查找的非递归实现,array是升序排列
     *
     * @param target 需要查找的数
     * @return 返回对应下标,-1表示没有找到
     */
    public int search(int target) {
        int left = 0;
        int right = array.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;

            if (array[mid] == target) {
                return mid;
            } else if (array[mid] > target) {
                // 向左查找
                right = mid - 1;
            } else {
                // 向右查找
                left = mid + 1;
            }
        }
        // 未找见
        return -1;
    }
}
